package mao.leetcode.others.leetcode377;

//使用深度优先搜索时间复杂度太高。
class Solution {
    private int res = 0;
    private int sum = 0;
    public int combinationSum4(int[] nums, int target) {
        dfs(nums,target);
        return res;
    }

    public void dfs(int[] nums,int target ){
        if(sum > target) return;
        if(sum == target){
            res++;
            return;
        }
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            dfs(nums,target);
            sum-=nums[i];
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,2,3};
        int target = 32;
        int i = solution.combinationSum4(nums, target);
        System.out.println(i);
    }
}